package sword_to_1;

import java.util.Arrays;

public class LeeCode_29 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(spiralOrder(new int[][]{{1, 2}, {3, 4}})));
        System.out.println(Arrays.toString(spiralOrder(new int[][]{{1, 2, 3 ,4}, {5, 6, 7, 8}, {9,10,11,12}})));
        System.out.println(Arrays.toString(spiralOrder(new int[][]{
                {1, 2, 3 ,4},
                {5, 6, 7, 8},
                {9,10,11,12},
                {13,14,15,16}})));
        System.out.println(Arrays.toString(spiralOrder(new int[][]{})));
        System.out.println(Arrays.toString(spiralOrder(new int[][]{
                {1,2,3,4,5},
                {6,7,8,9,10},
                {11,12,13,14,15},
                {16,17,18,19,20},
                {21,22,23,24,25}
        })));
    }
    // 上下左右 0 1 2 3
    private static int[] spiralOrder(int[][] matrix) {
        int m = matrix.length;
        if (m == 0)
            return new int[0];
        int n = matrix[0].length;
        int[] ans = new int[m * n];
        dfs(ans, 0, 0, 0 ,3, 0, n - 1, matrix, 0);
        return ans;
    }
    private static void dfs(int[] ans, int index, int i, int j, int dir, int ei, int ej, int[][] matrix, int count){
        if (index == ans.length){
            return;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        ans[index] = matrix[i][j];
        if (i == ei && j == ej){
            int newDir = 0;
            int newI = 0, newJ = 0;
            newI = m - 1 - ei;
            newJ = n - 1 - ej;
            if (count >= 2 && i != (m - 1) / 2 && (dir == 2 || dir == 0)){
                newI += newI < m / 2 ? 1 : -1;
            }
            if (count >= 2 && j != (n - 1) / 2  && (dir == 2 || dir == 0)){
                newJ += newJ < n / 2 ? 1 : -1;
            }
            switch (dir){
                case 1:{
                    newDir = 2;
                    dfs(ans, index + 1, i, j - 1, newDir, ei, newJ, matrix, count + 1);
                    break;
                }
                case 0:{
                    newDir = 3;
                    dfs(ans, index + 1, i, j + 1, newDir, i, newJ, matrix, count + 1);
                    break;
                }
                case 2:{
                    dfs(ans, index + 1, i - 1, j, newDir, newI, ej, matrix, count + 1);
                    break;
                }
                case 3:{
                    newDir = 1;
                    dfs(ans, index + 1, i + 1, j, newDir, newI, ej, matrix, count + 1);
                    break;
                }
            }
        }else {
            if (dir == 0){
                dfs(ans, index + 1, i - 1, j, dir, ei, ej, matrix, count);
            }else if (dir == 1){
                dfs(ans, index + 1, i + 1, j, dir, ei, ej, matrix, count);
            }else if (dir == 2){
                dfs(ans, index + 1, i, j - 1, dir, ei, ej, matrix, count);
            }else {
                dfs(ans, index + 1, i, j + 1, dir, ei, ej, matrix, count);
            }
        }
    }
}
